package com.lw.leetcode.binary.b;

import java.util.LinkedList;
import java.util.List;

/**
 * binary
 * 658. 找到 K 个最接近的元素
 *
 * @Author liw
 * @Date 2021/7/5 17:28
 * @Version 1.0
 */
public class FindClosestElements {

    public static void main(String[] args) {
        FindClosestElements test = new FindClosestElements();
        int[] arr = {1, 2, 3, 4, 5};
        int k = 4;
        int x = -1;
        List<Integer> closestElements = test.findClosestElements(arr, k, x);
        System.out.println(closestElements);
    }

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int index = find(arr, x);
        int length = arr.length;
        LinkedList<Integer> list = new LinkedList<>();
        int st = index;
        int end = index + 1;
        if (arr[index] == x) {
            list.add(arr[index]);
            st--;
            k--;
        }
        while (k > 0 && st >= 0 && end < length) {
            int a = Math.abs(arr[st] - x);
            int b = Math.abs(arr[end] - x);
            if (a > b) {
                list.add(arr[end]);
                end++;
            } else {
                list.addFirst(arr[st]);
                st--;
            }
            k--;
        }
        while (k > 0 && st >= 0) {
            list.addFirst(arr[st]);
            st--;
            k--;
        }
        while (k > 0 && end < length) {
            list.add(arr[end]);
            end++;
            k--;
        }
        return list;
    }

    private int find(int[] arr, int x) {
        int st = 0;
        int end = arr.length - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            int value = arr[m];
            if (value == x) {
                return m;
            } else if (value > x) {
                end = m - 1;
            } else {
                st = m;
            }
        }
        return st;
    }

}
